313. Super Ugly Number

1. Question

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the n^th super ugly number.

The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

2. Examples

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

3. Constraints

• 1 <= n <= 106
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] is guaranteed to be a prime number.
• All the values of primes are unique and sorted in ascending order.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/super-ugly-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        HashSet<Long> added = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        added.add(1L);
        queue.offer(1L);
        int ugly = 0;

        for (int i = 0; i < n; i++) {
            Long curr = queue.poll();
            ugly = Math.toIntExact(curr);
            for (int prime : primes) {
                long next = curr * prime;
                if (added.add(next)) {
                    queue.offer(next);
                }
            }

        }
        return ugly;
    }
}